package 极客算法训练营.chapter08;

import java.util.ArrayList;
import java.util.List;

public class N皇后 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        dfs(0, board, ans);
        return ans;
    }

    public void dfs(int depth, char[][] path, List<List<String>> ans) {
        if (depth == path.length) {
            ans.add(build(path));
            return;
        }
        for (int i = 0; i < path.length; i++) {
            if (valid(path, depth, i)) {
                path[depth][i] = 'Q';
                dfs(depth + 1, path, ans);
                path[depth][i] = '.';
            }
        }
    }

    private boolean valid(char[][] board, int x, int y) {
        if (x == 0) return true;
        //验证上方无皇后
        for (int i = 0; i < x; i++) {
            if (board[i][y] == 'Q') return false;
        }
        //验证左对角无皇后
        for (int i = y - 1; i >= 0 && x - y + i >= 0; i--) {
            if (board[x - y + i][i] == 'Q') return false;
        }
        //验证右对角无皇后
        for (int i = x - 1; i >= 0 && x + y - i <= board.length - 1; i--) {
            if (board[i][x + y - i] == 'Q') return false;
        }
        return true;
    }

    public List<String> build(char[][] board) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            res.add(new String(board[i]));
        }
        return res;
    }
}
